import java.util.PriorityQueue;

//数据流的中位数
//测试链接： https://leetcode.cn/problems/find-median-from-data-stream/
public class MedianFinder {
    /**
     *需要保持大根堆大于等于小根堆的数量，并且不能超过1
     */
    //大根堆存较小的值
    PriorityQueue<Integer> bigHeap;
    //小根堆存较大的值
    PriorityQueue<Integer> smallHeap;

    public MedianFinder() {
        bigHeap = new PriorityQueue<>((a,b) -> (b-a) );
        smallHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if(bigHeap.isEmpty()){  //首次加入放大根堆
            bigHeap.add(num);
            return;
        }

        if(num < bigHeap.peek()){
            bigHeap.add(num);
        }else{
            smallHeap.add(num);
        }

        //调整堆的数量保证：小根堆的数量小于等于大根堆，并且差值不能超过1
        while(smallHeap.size() > bigHeap.size()){
            bigHeap.add(smallHeap.poll());
        }

        while(bigHeap.size() - smallHeap.size() > 1 ){
            smallHeap.add(bigHeap.poll());
        }

    }

    //
    public double findMedian() {
        if(smallHeap.isEmpty()){
            return bigHeap.peek();
        }
        if(bigHeap.size() != smallHeap.size()){
            return bigHeap.peek() * 1.0;
        }
        else {
            return ( bigHeap.peek() + smallHeap.peek() ) / 2.0;
        }
    }
}
